package com.ligure;

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class DoubleLinkedList<T> {
    private static class Node<T> {
        private T data;
        private Node<T> prev;
        private Node<T> next;

        public Node(Node<T> prev, T data, Node<T> next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size;

    public void addHead(T data) {
        final Node hNode = head;
        final Node newNode = new Node(null, data, hNode);
        if (hNode == null) {
            tail = newNode;
        } else {
            hNode.prev = newNode;
        }
        head = newNode;
        size++;
    }

    public void addTail(T data) {
        final Node tNode = tail;
        final Node newNode = new Node(tNode, data, null);
        if (tNode == null) {
            head = newNode;
        } else {
            tNode.next = newNode;
        }
        tail = newNode;
        size++;
    }

    public boolean add(T data) {
        addTail(data);
        return true;
    }

    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入超出范围");
        }
        if (index == 0) {
            addHead(data);
        } else if (index == size) {
            addTail(data);
        } else {
            final Node node = get(index);
            final Node pred = node.prev;
            final Node newNode = new Node(pred, data, node);
            node.prev = newNode;
            if (pred == null) {
                head = newNode;
            } else {
                pred.next = newNode;
            }
            size++;
        }
    }

    public T set(int index, T data) {
        final Node<T> node = get(index);
        T oldData = node.data;
        node.data = data;
        return oldData;
    }

    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("查找超出范围");
        }
        if (index < (size >> 1)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node node = tail;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    public T removeHead() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        final T data = head.data;
        final Node<T> next = head.next;
        head.data = null;
        head.next = null;
        head = next;
        if (next == null) {
            tail = null;
        } else {
            next.prev = null;
        }
        size--;
        return data;
    }

    public T removeTail() {
        if (tail == null) {
            throw new NoSuchElementException();
        }
        final T data = tail.data;
        final Node<T> pred = tail.prev;
        tail.data = null;
        tail.prev = null;
        tail = pred;
        if (pred == null) {
            head = null;
        } else {
            pred.next = null;
        }
        size--;
        return data;
    }

    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("删除超出范围");
        }
        if (index == 0) {
            return removeHead();
        } else if (index == size - 1) {
            return removeTail();
        } else {
            final Node<T> node = get(index);
            return unlink(node);
        }
    }

    public boolean remove(Object o) {
        Node<T> node = head;
        if (o == null) {
            while (node != null && node.data != null) {
                node = node.next;
            }
        } else {
            while (node != null && !o.equals(node.data)) {
                node = node.next;
            }
        }
        if (node != null) {
            unlink(node);
            return true;
        }
        return false;
    }

    public boolean offer(T data) {
        return add(data);
    }

    public T peek() {
        return (head == null) ? null : head.data;
    }

    public T poll() {
        return (head == null) ? null : removeHead();
    }

    private T unlink(Node<T> node) {
        final Node<T> pred = node.prev;
        final Node<T> next = node.next;
        final T data = node.data;
        if (pred == null) {
            head = next;
        } else {
            pred.next = next;
            node.prev = null;
        }
        if (next == null) {
            tail = pred;
        } else {
            next.prev = pred;
            node.next = null;
        }
        node.data = null;
        size--;
        return data;
    }

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node n = head; n != null; n = n.next) {
            result[i++] = n.data;
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer("[");
        for (Node n = head; n != null; n = n.next) {
            if (n.next != null) {
                buffer.append(n.data).append(',');
            } else {
                buffer.append(n.data);
            }
        }
        buffer.append(']');
        return buffer.toString();
    }

    public int size() {
        return size;
    }

}